<?php
	class Arbol extends MyDebuger {
		/* elementos */
		private $elementos	= Array();
		/* arbol procesado */
		private $arbol			= Array();
		/* peso del arbol */
		private $peso			= 0;
		/* cantidad de nodos del arbol */
		private $cantNodes	= 0;
		/* altura del arbol */
		private $altura		= 0;
		/* cantidad maxima de nodos */
		private $maxNodes		= 0;
		/* lista de nodos hoja */
		private $nodosHoja	= Array();

		public function __construct($debuging = False) {
			try {
				try {
					/* creamos el padre */
					parent::__construct(__CLASS__);
					/* verificamos si habilitamos la depuracion */
					if ($debuging)
						/* habilitamos la depuracion */
						$this->enableHtmlDebug();
				} catch (ErrorException $e) {
					/* capturamos todos los errores y los transformamos en mi excepcion */
					$this->convertToMyException($e);
				}
			} catch (MyException $e) {
				/* si se produjo una excepcion la manejamos con el metodo 'show' */
				$this->show($e->getMensaje($this->html));
			}
		}

		public static function procesarArbol($arrayArbol, $debuging = False) {
			/* creamos la instancia */
			$arbol = new Arbol($debuging);
			/* cargamos los elementos */
			$arbol->loadElements($arrayArbol);
			/* almacenamos el peso del arbol */
			$arbol->saveCantNodos();
			/* iniciamos el proceso */
			$arbol->procesar();
			/* almacenamos la altura del arbol */
			$arbol->getAltura();
			/* almacenamos la cantidad maxima de nodos */
			$arbol->saveMaxNodes();
			/* armamos la estructura de salida */
			$arbol->armarEstructura();
			/* retornamos el arbol */
			return $arbol->arbol;
		}

		public static function mostrarArbol($arrayArbol, $debuging = False) {
			/* creamos la instancia */
			$arbol = new Arbol($debuging);
			/* mostramos el arbol */
			$arbol->showArbol($arrayArbol['ARBOL']);
			/* mostramos los datos del arbol */
			$arbol->showData($arrayArbol);
		}

		private function showData($arrayArbol) {
			/* iniciamos una tabla */
			echo '<TABLE>';
			/* mostramos el peso del arbol */
			echo '<TR><TD style=\'font-weight: bold;\'>Peso:</TD><TD>' . $arrayArbol['PESO'] . '</TD></TR>';
			/* mostramos la altura del arbol */
			echo '<TR><TD style=\'font-weight: bold;\'>Altura:</TD><TD>' . $arrayArbol['ALTURA'] . '</TD></TR>';
			/* mostramos el peso del arbol */
			echo '<TR><TD style=\'font-weight: bold;\'>Cantidad de Nodos:</TD><TD>' . $arrayArbol['CANTNODES'] . '</TD></TR>';
			/* mostramos la cantidad maxima de nodos */
			echo '<TR><TD style=\'font-weight: bold;\'>Cantidad Maxima de Nodos:</TD><TD>' . $arrayArbol['MAXNODES'] . '</TD></TR>';
			/* mostramos los nodos hoja */
			echo '<TR><TD style=\'font-weight: bold;\'>Nodos Hoja:</TD><TD><TABLE><TR>';
			foreach ($arrayArbol['NODOSHOJA'] AS $nodoHoja)
				echo $nodoHoja . '&nbsp;&nbsp;';
			echo '</TR></TABLE></TD></TR>';
		}

		private function armarEstructura() {
			/* almacenamos el arbol */
			$this->arbol = Array('ARBOL' => $this->arbol);
			/* almacenamos la altura */
			$this->arbol['ALTURA'] = $this->altura;
			/* almacenamos el peso */
			$this->arbol['PESO'] = $this->peso;
			/* almacenamos la cantidad de nodos */
			$this->arbol['CANTNODES'] = $this->cantNodes;
			/* almacenamos la cantidad maxima de nodos */
			$this->arbol['MAXNODES'] = $this->maxNodes;
			/* almacenamos los nodos hoja */
			$this->arbol['NODOSHOJA'] = $this->nodosHoja;
		}

		private function loadElements($elementos) {
			/* mostramos un mensaje */
			$this->show('Cargando elementos del arbol..', False);
			/* almacenamos los elementos */
			$this->elementos = $elementos;
			/* mostramos ok al mensaje */
			$this->showOK();
		}

		private function saveCantNodos() {
			/* guardamos la cantidad de nodos del arbol */
			$this->cantNodes = count($this->elementos);
		}

		private function saveMaxNodes() {
			$this->maxNodes = 2;
			/* almacenamos la cantidad maxima del arbol */
			for ($i = 1; $i < $this->altura; $i++)
				$this->maxNodes *= 2;
			$this->maxNodes -= 1;
		}

		private function procesar() {
			try {
				try {
					/* ordenamos los elementos */
					$this->ordenarElementos();
					/* armamos el arbol y lo almacenamos como resultado */
					$this->arbol = $this->separarArbol($this->elementos, $this->getMedio($this->elementos));
				} catch (ErrorException $e) {
					/* capturamos todos los errores y los transformamos en mi excepcion */
					$this->convertToMyException($e);
				}
			} catch (MyException $e) {
				/* si se produjo una excepcion la manejamos con el metodo 'show' */
				$this->show($e->getMensaje($this->html));
			}
		}

		private function ordenarElementos() {
			/* mostramos un mensaje */
			$this->show('Ordenando elementos del arbol..', False);
			/* ordenamos los elementos */
			sort($this->elementos);
			/* mostramos ok al mensaje */
			$this->showOK();
		}

		private function getMedio($elements) {
			/* mostramos un mensaje */
			$this->show('Obteniendo medio..', False); $this->showOK();
			/* retornamos el valor del medio */
			return $elements[round((count($elements) - 1) / 2)];
		}

		private function separarArbol($elements, $medio) {
			/* mostramos un mensaje */
			$this->show('Separando nodo ' . $this->italic($medio) . '..', False);
			/* creamos un array temporal para el arbol izquierdo */
			$arrayIzq = Array();
			/* creamos un array temporal para el arbol derecho */
			$arrayDer = Array();
			/* recorremos los elementos */
			foreach ($elements AS $nodo) {
				/* verificamos si es menor al elemento central */
				if ($nodo > $medio)
					/* lo almacenamos en el arbol derecho */
					$arrayDer[] = $nodo;
				/* verificamos si es mayor al elemento central */
				elseif ($nodo < $medio)
					/* lo almacenamos en el arbol izquierdo */
					$arrayIzq[] = $nodo;
			}
			/* mostramos ok al mensaje */
			$this->showOK();
			/* verificamos si existen valores en el nodo izquierdo */
			if (count($arrayIzq) > 0)
				/* separamos el nodo izquierdo */
				$arrayIzq = $this->separarArbol($arrayIzq, $this->getMedio($arrayIzq));
			/* verificamos si existen valores en el nodo derecho */
			if (count($arrayDer) > 0)
				/* separamos el nodo derecho */
				$arrayDer = $this->separarArbol($arrayDer, $this->getMedio($arrayDer));
			/* retornamos el arbol separado */
			return Array(
				/* retornamos el numero del nodo */
				'NODO'	=> $medio,
				/* retornamos el subarbol izquierdo */
				'IZQ'		=> $arrayIzq,
				/* retornamos el subarbol derecho */
				'DER'		=> $arrayDer
			);
		}

		private function getAltura() {
			if (count($this->arbol['IZQ']) > 0)
				$this->dameAltura($this->arbol['IZQ']);
			if (count($this->arbol['DER']) > 0)
				$this->dameAltura($this->arbol['DER']);
			$this->altura = $this->altura + 2;
		}

		private function dameAltura($nodo, $cantidadActual = 0) {
			$this->show('Nodo: '.$nodo['NODO'].' Actual: ' . $cantidadActual);
			if (count($nodo['IZQ']) == 0 && count($nodo['DER']) == 0) {
				if ($cantidadActual > $this->altura) {
					$this->show('Altura nueva: ' . $cantidadActual . ' Vieja: ' . $this->altura);
					$this->altura = $cantidadActual;
				}
				$this->peso++;
				$this->nodosHoja[] = $nodo['NODO'];
			} else {
				if (count($nodo['IZQ']) > 0 && count($nodo['DER']) > 0) {
					$cantidadActual++;
					$this->dameAltura($nodo['IZQ'], $cantidadActual);
					$this->dameAltura($nodo['DER'], $cantidadActual);
				} else {
					if (count($nodo['IZQ']) > 0) {
						$cantidadActual++;
						$this->dameAltura($nodo['IZQ'], $cantidadActual);
					}
					if (count($nodo['DER']) > 0) {
						$cantidadActual++;
						$this->dameAltura($nodo['DER'], $cantidadActual);
					}
				}
			}
		}

		private function showArbol($arbol, $friend = Array()) {
			echo '<TABLE border=\'0\' style=\'border-collapse: collapse;\'>';
				echo '<TR><TD colspan=\'2\' style=\'text-align: center; min-width: 50px;\'>';
					echo '<TABLE border=\'1\' style=\'border-collapse: collapse;\' align=\'center\'>';
						echo '<TR><TD style=\'background-color: #DDD; min-width: 25px; text-align: center;\'>' . $arbol['NODO'] . '</TD></TR>';
					echo '</TABLE>';
				echo '</TD></TR>';
				echo '<TR><TD style=\'height:15px; text-align:center;\'></TD></TR>';
				echo '<TR><TD style=\'width: 50%; vertical-align: top;\'>';
					if (count($arbol['IZQ']) == 0 && count($arbol['DER']) == 0) {
						echo '<TABLE>';
							echo '<TR>';
								echo '<TD colspan=\'2\' style=\'min-width: '. (count($friend) == 0 || isset($friend['NODO']) ? '50' : '100') .'px;\'></TD>';
							echo '</TR>';
						echo '</TABLE>';
					} else {
						if (count($arbol['IZQ']) > 0)
							$this->showArbol($arbol['IZQ'], $arbol['DER']);
						else
							echo '<TABLE><TR><TD style=\'min-width: 50px;\'></TD></TR></TABLE>';
						echo '</TD><TD style=\'width: 50%; vertical-align: top;\'>';
						if (count($arbol['DER']) > 0)
							$this->showArbol($arbol['DER'], $arbol['IZQ']);
						else
							echo '<TABLE><TR><TD style=\'min-width: 50px;\'></TD></TR></TABLE>';
					}
				echo '</TD>';
			echo '</TABLE>';
		}
	}
?>